package 栈;

public class No85最大矩形 {

    /**
     * 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
     *
     * 示例 1：
     * 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
     * 输出：6
     * 解释：最大矩形如上图所示。
     * 示例 2：
     * 输入：matrix = []
     * 输出：0
     *  
     * 提示：
     * rows == matrix.length
     * cols == matrix[0].length
     * 0 <= row, cols <= 200
     * matrix[i][j] 为 '0' 或 '1'
     */


    public int maximalRectangle(char[][] matrix) {
        /**
         * 1.左起点开始 1的个数  此方法很好
         * 2.算出每层的高,调用No84的函数  略
         */
        if(matrix.length<1){
            return 0;
        }
        return method1(matrix);
    }

    private int method1(char[][] martix){

        int allLength=martix.length;
        int itemLength=martix[0].length;
        int[][] oneCount=new int[allLength][itemLength];

        //base 竖排
        for (int i = 0; i < allLength; i++) {
            if(martix[i][0]=='1'){
                oneCount[i][0]=1;
            }
        }

        for (int i = 0; i < allLength; i++) {
            for (int j = 1; j < itemLength; j++) {
                if(martix[i][j]!='0'){
                    oneCount[i][j]=oneCount[i][j-1]+1;
                }
            }
        }

        int result=0;

        for (int i = 0; i < allLength; i++) {
            for (int j = 0; j < itemLength; j++) {

                if(oneCount[i][j]!=0) {
                    int area = oneCount[i][j];
                    int minWidth=oneCount[i][j];//注意取每层的minWidth
                    for (int k = i - 1; k >= 0; k--) {
                        if(oneCount[k][j]!=0) {
                            minWidth=Math.min(minWidth,oneCount[k][j]);
                            area = Math.max(area, minWidth * (i - k + 1));
                        }else{
                            break;
                        }
                    }
                    result=Math.max(result,area);
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        No85最大矩形 n=new No85最大矩形();
        char[][] arr={
                {'1','0','1','0','0'},
                {'1','0','1','1','1'},
                {'1','1','1','1','1'},
                {'1','0','0','1','0'}
        };
        int result = n.method1(arr);
        System.out.println(result);
    }

}
